#include "HaFuManTree.h"

/**
 * 构造哈夫曼树
 * @param node
 * @param length 节点数组的长度
 */
void CreateHalffmanTree(HaffNode *node, int length) {
    /* 只是节点,非树 */
    if (length <= 1) {
        return;
    }

    SortHaffmanNode(node, length);

    /* 构建一个以 node 数组最后两位节点组成的父节点 */
    HaffNode parent;
    /* 排序后 length-1就是权重最小的节点 */
    left[length] = node[length - 1];
    /* length-2就是权重第二小的节点 */
    right[length] = node[length - 2];
    parent.weight = left[length].weight + right[length].weight;
    parent.leftChild = &left[length];
    parent.rightChild = &right[length];
    /* parent节点的data不用赋值 */
    /* 将倒数第二位替换为 parent节点,数组长度-1,递归创建哈夫曼树 */
    node[length - 2] = parent;
    CreateHalffmanTree(node, length - 1);
}


/**
 * 冒泡排序,默认权值大小降序排序
 * @param node
 * @param length
 */
void SortHaffmanNode(HaffNode *node, int length) {
    HaffNode tempNode;
    for (int i = 0; i < length - 1; i++) {
        for (int j = 0; j < length - i - 1; j++) {
            if (node[j].weight < node[j + 1].weight) {
                tempNode = node[j];
                node[j] = node[j + 1];
                node[j + 1] = tempNode;
            }
        }
    }
}

/**
 * 编码过程(压缩)
 * @param node 节点数组
 * @param tempCode  编码后的字符数组(keepCode)
 * @param index  当前操作字符数组下标
 */
void Coding(HaffNode *node, char *tempCode, int index) {
    if (!node) {
        return;
    }
    /* 处理叶子节点: 所有的字符节点都是叶节点 */
    if (node->leftChild == NULL || node->rightChild == NULL) {
        /* 将编码复制到编码数组中去 tempCode中保存的就是{'0','0'} */
        tempCode[index] = '\0';
        /* 可以强制转换数据类型为 int */
        strcpy(code[node->data - 0], tempCode);

        return;
    }

    /* 左分支编码为'0',右分支编码为'1' */
    tempCode[index] = '0';
    Coding(node->leftChild, tempCode, index + 1);
    tempCode[index] = '1';
    Coding(node->rightChild, tempCode, index + 1);

}


/**
 * 解码过程(解压缩)
 * @param node
 * @param flag  0(走向左树) | 1(走向右树)  标志位
 * @return
 */
HaffNode *deCoding(HaffNode *node, int flag) {
    /* 如果标志位为 0,走向左树 */
    if (flag == 0) {
        return node->leftChild;
    }
    /* 如果标志位为 1,走向右树 */
    if (flag == 1) {
        return node->rightChild;
    }

    return NULL;
}